In wireless mesh networks, a single-hop or multi-hop path needs to be selected to forward data frames/packets from a source node/mesh point to a destination node/mesh point. The path selection is based on a metric. Such a routing metric is important for optimizing the design of routing and forwarding mechanisms in mesh networks. Routing metrics for wired or optical networks do not account for the fact that nodes share the communications medium in wireless networks. Metrics that do exist for wireless mesh networks do not consider factors such as traffic load and error rate on the radio link.
Most of the current mesh routing protocols use the minimum hop count as the metric to make the path selection decision. With this approach, the quality of the radio link and the traffic load on the link is not considered. The path with the minimum number of hops is selected to forward the data frames. However, minimal hop count paths can have poor performance because they tend to include radio links between distant nodes and the quality of links along the path may not be good, let alone optimal. The radio links with a long physical span can be lossy, incurring a number of retransmissions and a low physical layer data rate. Many radio transmission systems, for example IEEE 802.11 radios, adapt the physical layer data rate depending on the link quality. This actually results in poor throughput and reduces the efficiency of network utilization compared to selecting a path with more hops but better link quality.
A prior art metric called “expected transmission count” (EXT) has been used as a routing metric. This metric estimates the number of retransmissions needed to successfully send a unicast packet by measuring the loss rate of broadcast packets between pairs of neighboring nodes. The routing protocol selects the path with the smallest total sum of the expected number of retransmissions. EXT takes the link loss rate, i.e. the number of needed retransmissions, into consideration but it does not take the link data rate and link load into account. Two links with different data rates may have the same loss rate. A heavily loaded link may incur a low loss rate and may be selected to include in the path so that this link becomes more loaded and congestion occurs.
Another known metric called “per-hop round trip time” (RTT) has been proposed as the routing metric. This metric estimates the round trip delay of unicast probing packets between neighboring nodes. The routing protocol selects the path with the lowest total sum of RTTs. The RTT metric implicitly accounts for the link quality and traffic load to avoid heavily loaded or lossy links. However, one problem with this metric is that it requires that every node in the mesh network to send probe packets to each of its neighbors, which introduces network overhead. Furthermore, this metric does not explicitly take the link data rate into account.
In radio/wireless networks, both the link/channel quality and load varies so the value of link metric changes frequently. This may cause the path to change frequently, leading to route instability. All the above measures do not consider how to maintain the route stability while achieving quick response to the link state and network topology changes. Clearly, a metric is needed for improved routing and forwarding mechanisms for wireless mesh networks that accounts for radio link quality and traffic load as well as route stability even in the face of rapidly changing link/channel quality and load variations.